package com.wxg.algorithm.chapter02.comparable;

import com.wxg.algorithm.chapter02.util.SortTestHelper;
import com.wxg.algorithm.common.ISort;

/**
 * 插入排序
 *
 * @param <T>
 */
public class InsertionSort<T extends Comparable> implements ISort<T> {
    @Override
    public void sort(T[] arr) {
        for(int i=1; i<arr.length; i++){

            // 寻找元素 arr[i] 合适的插入位置
            for(int j=i; j > 0; j--) {
                if(arr[j-1].compareTo(arr[j]) > 0){
                    T temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }else {
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        InsertionSort<Integer> is = new InsertionSort<>();
        SelectionSort<Integer> ss = new SelectionSort<>();
        int n = 40000;
        Integer[] intArr = SortTestHelper.generateRandomArray(n, 0, n);

        Integer[] intArr2 = SortTestHelper.copyIntArray(intArr);

        SortTestHelper.testSort(is, intArr);
        SortTestHelper.testSort(ss, intArr2);
    }
}
